package com.origin.niuke.tree;

import general_class.TreeNode;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/7/21 22:09
 * 二叉搜索树与双向链表
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
 * 算法：中序遍历
 */
public class BM30 {

    TreeNode preNode;

    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) return null;
        TreeNode ans = pRootOfTree;
        while (ans.left != null) ans = ans.left;
        inOrder(pRootOfTree);
        return ans;
    }

    void inOrder(TreeNode node) {
        if (node == null) return;
        inOrder(node.left);
        node.left = preNode;
        if (preNode != null) preNode.right = node;
        preNode = node;
        inOrder(node.right);
    }

}
